package com.dmall.graph.bfs.app;

import java.util.*;

public class Leetcode773 {

    private static final String end = "123450";
    private int zeroIndex = -1;

    private int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public int slidingPuzzle(int[][] board) {
        String start = boardToString(board);
        if (end.equals(start)) {
            return 0;
        }
        Map<String, Integer> visited = new HashMap<>();
        Queue<String> queue = new LinkedList<>();
        visited.put(start, 0);
        queue.add(start);
        while (!queue.isEmpty()) {
            String cur = queue.remove();
            for (String next : getNexts(cur)) {
                if (!visited.containsKey(next)) {
                    visited.put(next, visited.get(cur) + 1);
                    queue.add(next);
                    if (end.equals(next)) {
                        return visited.get(next);
                    }
                }
            }
        }
        return -1;
    }

    public Set<String> getNexts(String cur) {
        Set<String> set = new HashSet<>();
        int[][] board = stringToBoard(cur);
        int x0 = zeroIndex / 3;
        int y0 = zeroIndex % 3;
        for (int i = 0; i < dirs.length; i++) {
            int nextx = x0 + dirs[i][0];
            int nexty = y0 + dirs[i][1];
            if (inArea(nextx, nexty)) {
                swap(board, x0, y0, nextx, nexty);
                set.add(boardToString(board));
                swap(board, x0, y0, nextx, nexty);
            }
        }
        return set;
    }

    public void swap(int[][] board, int x1, int y1, int x2, int y2) {
        int temp = board[x1][y1];
        board[x1][y1] = board[x2][y2];
        board[x2][y2] = temp;
    }

    private String boardToString(int[][] board) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                sb.append(board[i][j]);
            }
        }
        return sb.toString();
    }

    private int[][] stringToBoard(String s) {
        int[][] board = new int[2][3];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 3; j++) {
                char cur = s.charAt(i * 3 + j);
                board[i][j] = cur - '0';
                if (cur == '0') {
                    zeroIndex = i * 3 + j;
                }
            }
        }
        return board;
    }

    private boolean inArea(int x, int y) {
        return x >= 0 && x < 2 && y >= 0 && y < 3;
    }

    public static void main(String[] args) {
        int[][] board = {{4, 1, 2}, {5, 0, 3}};
        Leetcode773 leetcode773 = new Leetcode773();
        System.out.println(leetcode773.slidingPuzzle(board));
    }
}
